#include "table.h"

/**
 * shell 插入排序算法
 * @param {table}  table 待排序表
 * @return {void}
 */
void shellinsertsort(table *tab)
{
    int i, j, d;
    d = tab->length / 2;

    while (d >= 1)
    {
        for (i = d + 1; i <= tab->length; i++)
        {
            tab->r[0] = tab->r[i];
            j = i - d;

            while (j > 0 && tab->r[0].key < tab->r[j].key)
            {
                tab->r[j + d] = tab->r[j];
                j = j - d;
            }

            tab->r[j + d] = tab->r[0];
        }

        d = d / 2;
    }
}

int main()
{
    table tab;
    int i;
    int arr[10] = {0, 9, 1, 5, 8, 3, 7, 4, 6, 2};
    tab.length = 9;
    for (i = 1; i <= tab.length; i++)
    {
        tab.r[i].key = arr[i];
    }
    shellinsertsort(&tab);
    for (i = 1; i <= tab.length; i++)
    {
        printf("%d ", tab.r[i].key);
    }
    return 0;
}